#!/usr/bin/env python
# Create: 2020-04-27 21:21:51
__author__ = '749B'
"""https://leetcode-cn.com/problems/valid-parentheses/"""

from typing import List

class Solution:
    def isValid(self, s: str) -> bool:
        l = []  # type: List[str] 
        for i in s:
            if i in '([{':
                l.append(i)
            elif i == ')':
                if not l : return False
                if l.pop() != '(':
                    return False
            elif i == ']':
                if not l : return False
                if l.pop() != '[':
                    return False
            elif i == '}':
                if not l : return False
                if l.pop() != '{':
                    return False
            else:
                return False
        if l:
            return False
        return True

    def isValid2(self, s: str) -> bool:
        l = []  # type: List[str] 
        m = {"(": ")", "[": "]", "{": "}"}
        for i in s:
            if i in m:
                l.append(i)
            else:
                if not l:
                    return False
                if i != m.get(l.pop()):
                    return False
        return not l

    def isValid3(self, s: str) -> bool:
        """虽然慢，但是够简单"""
        while '()' in s or '[]' in s or '{}' in s:
            s = s.replace('()', '')
            s = s.replace('[]', '')
            s = s.replace('{}', '')
        return s == ''

